Sau khi bị xử bắn, thi hài Nguyễn Văn Trỗi được chôn cất tại nghĩa trang Văn Giáp ở Giồng Ông Tố (nay thuộc phường Bình Trưng Đông, thành phố Thủ Đức, Thành phố Hồ Chí Minh). Ngày 15 tháng 4 năm 2018, phần mộ Nguyễn Văn Trỗi được chuyển từ nghĩa trang Văn Giáp (quận 2) về khu vực các phần mộ tiêu biểu Nghĩa trang liệt sĩ Thành phố Hồ Chí Minh (quận 9) theo nguyện vọng của gia đình anh.[16]

Hai ngày sau khi hi sinh, Nguyễn Văn Trỗi được truy tặng danh hiệu Anh hùng lực lượng vũ trang nhân dân vào ngày 17 tháng 10 năm 1964.[17] Ngoài ra còn có các danh hiệu Đảng viên Nhân dân Cách mạng miền Nam và Huân chương Thành đồng hạng nhất của Mặt trận Dân tộc Giải phóng miền Nam Việt Nam.

Tại Hội nghị Ban Chấp hành Thành đoàn TP HCM khóa II (năm 1982), các đại biểu đã nhất trí chọn ngày 15/10 – Ngày liệt sĩ Nguyễn Văn Trỗi hy sinh là Ngày truyền thống thanh niên công nhân TP Hồ Chí Minh.

Năm 2012, kỷ niệm 48 năm ngày mất, nhà tưởng niệm Nguyễn Văn Trỗi được khánh thành trong khuôn viên nghĩa trang liệt sĩ huyện Điện Bàn (Quảng Nam). Tên Nguyễn Văn Trỗi được đặt cho nhiều con đường, nhiều trường học trên khắp Việt Nam.